package com.weightedQuickUnion;

import com.UF;

import java.util.Arrays;

/**
 * @author 罗俊华
 * @date 2021/5/10 - 8:29 上午
 */
public class WeightedQuickUnion implements UF {

    protected int[] id;

    private int count;

    private int[] treeHeight; // 代表根触点的树对应的高度

    public WeightedQuickUnion(int count) {
        this.count = count;
        this.id = new int[count];
        this.treeHeight = new int[count];
        for (int i = 0; i < this.id.length; i++) {
            this.id[i] = i;
            this.treeHeight[i] = 1; // 初始化每一课树的深度为1
        }

    }

    @Override
    public void union(int p, int q) {


        //        找到触点q的根触点
        int rootContactPointQ = this.find(q);

        //        找到触点p的根触点
        int rootContactPointP = this.find(p);

        if (rootContactPointP == rootContactPointQ) {
            return;
        }

//      获得两个根触点的树的对应高度
        int pRootContactTreeHeight = this.treeHeight[rootContactPointP];
        int qRootContactTreeHeight = this.treeHeight[rootContactPointQ];

        if (pRootContactTreeHeight < qRootContactTreeHeight) {

            //            将触点p所在的树（小树，触点p的根触点）指向触点q所在的树（大树，触点q的根触点）
            System.out.printf("将触点【%d】所在的树（小树，即触点【%d】的根触点【%d】）指向触点【%d】所在的树（大树，即触点【%d】的根触点【%d】）\n", p, p, rootContactPointP, q, q, rootContactPointQ);
            this.id[rootContactPointP] = rootContactPointQ;

            this.treeHeight[rootContactPointQ] +=  this.treeHeight[rootContactPointP];
        } else {
            this.id[rootContactPointQ] = rootContactPointP;
            System.out.printf("将触点【%d】所在的树（小树，即触点【%d】的根触点【%d】）指向触点【%d】所在的树（大树，即触点【%d】的根触点【%d】）\n", q, q, rootContactPointQ, p, p, rootContactPointP);
//            更新大树的高度，因为是小树接到了大树的根节点上，所以小树的高度不变
            this.treeHeight[rootContactPointP] +=  this.treeHeight[rootContactPointQ];
        }
        count--;
    }

    /**
     * 因为找到了根节点之后，根节点的触点值和分量是相同的，所以返回触点即可
     *
     * @param p
     * @return
     */
    @Override
    public int find(int p) {
        while (this.id[p] != p) {
            p = this.id[p];
        }
        return p;
    }

    @Override
    public boolean connected(int p, int q) {
        return this.find(p) == this.find(q);
    }

    @Override
    public int count() {
        System.out.println("触点对应的树是:" + Arrays.toString(this.id));
        System.out.println("根触点（树）对应的高度是：" + Arrays.toString(this.treeHeight));
        return this.count;
    }
}
